Problem statement: zenit13ckb

Ďalšou hrou, ktorej sa budeme venovať, je starý dobrý Tetris. Možno neviete, ale táto hra vznikla na území bývalého Sovietskeho zväzu v roku 1984. V našej verzii padajú z vrchu šachty stavebné kocky nasledovných tvarov

.............................
.XXX...X.....X....X...X....X.
..X....XX...XX....X...X...XX.
..X....XX...XX...XX...XX..X..
.............................

V tejto úlohe budeme hľadať odpoveď na jednoduchú otázku: je možné pre dané R pri vhodnom poradí padania tvarov kociek zaplniť šachtu tak, aby bolo vyplnených práve R riadkov a nič viac? Šachta má šírku 5 malých štvorčekov. Každú kocku môžeme použiť ľubovoľne veľa krát (aj nula). V tejto úlohy kocky pri vyplnení riadku nemiznú.

...................
...X..XX....X..XX..
..XX...XX..XX...XX.
..X........X.......
...................

Všimnite si, že napríklad takýto tvar len otáčaním nie je možné dosiahnuť

......
..X...
..XX..
...X..
......

Na vstupe je jediné číslo R (1 ≤ R ≤ 50). Ak sa nedá uvedenou sadou kociek vyplniť šachta veľká R×5, potom vypíšte NEDA SA. V opačnom prípade vypíšte príklad korektného umiestnenia kociek do šachty. V tejto úlohe zanedbajte proces umiestnenia kocky na miesto (ako keby sme mali dosť času každú kocku natočiť ako potrebujeme a počas jej umiestňovania na miesto nám nič nezavadzalo).

Ak riešenie existuje, výstup by mal obsahovať presne R riadkov. Na každom z nich musí byť práve 5 znakov, tie by mali byť veľké písmená anglickej abecedy. Na výpis každej kocky použite jedno písmeno. Kocky, ktoré v nákrese susedia musia byť vypísané rôznymi písmenami (je povolené a niekedy aj nutné priradiť dvom rôznym nesusediacim kockám rovnaké písmeno). Pod susednosťou dvoch štvorčekov rozumieme zdieľanie celej hrany. Každý štvorček má teda najviac štyroch susedov. Spomedzi všetkých riešení vypíšte ľubovoľné. Na priradení písmen kockám nezáleží.

5 

BBEEE
BBCEE
ABCCC
AACDD
AADDD   

1 

NEDA SA 

7 

FFFDD
FCCAD
DCCAD
DCAAA
DDCCB
ACCCB
AAABB